﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Collections;

namespace GA_Cube2
{
    class Program
    {
        public static int MIND = 50;  //种群大小，个体数目
        public static int MAXGEN = 3000; //最大遗传代数
        public static double GGAP = 0.6; //种群代沟
        public static double Pm = 0.15;  //变异概率
        public static int L = 6;        //个体长度
        public static int N = 5;         //魔方N*N规模
        public static int MINCHUNCK = 4;
        public static StreamWriter sw = File.CreateText(@"maxf.txt");

        public static int[,] cube = new int[N, N];


        public static Random rand = new Random();

        public static void Main(string[] args)
        {
            readCube(@"cube.txt");
            Population pop = new Population();
            pop.init();
            pop.deviration();

            sw.Flush();
            sw.Close();
        }


        public static void readCube(String filename)
        {
            StreamReader sr = new StreamReader(filename);
            String str;
            for (int j = 0; j < N; j++)
            {
                str = sr.ReadLine();
                String[] strs = str.Trim().Split(' ');
                for (int i = 0; i < N; i++)
                {
                    cube[i, j] = Int32.Parse(strs[i]);
                }
            }
        }




        /// <summary>
        /// 旋转方式作为种群的基因
        /// </summary>
        public class Gene
        {
            public int x, y;  //旋转中心点
            public int radix; //旋转半径
            public int func;  //旋转方式，0为90度，1为180读，2为270，顺时针旋转


            public Gene()
            {

            }

            public void copyGene(Gene a)
            {
                this.x = a.x;
                this.y = a.y;
                this.radix = a.radix;
                this.func = a.func;

            }

            public void randomGene()
            {
                this.x = rand.Next(1, N);
                this.y = rand.Next(1, N);
                int maxRadix = min(N - this.x, min(N - this.y, min(this.x, this.y)));
                this.radix = rand.Next(1, maxRadix + 1);
                this.func = rand.Next(0, 3);
            }

            public int min(int a, int b)
            {
                return (a < b ? a : b);
            }

            public void printGene()
            {
                System.Console.WriteLine("(" + this.x + "," + this.y + "," + this.radix + "," + this.func + ")");
            }
        }

        /// <summary>
        /// 长度为L的个体Entity，每个个体包含L个基因Gene
        /// </summary>
        public class Entity
        {
            public Gene[] entity;

            public Entity()
            {
                this.entity = new Gene[L];
            }

            public void copyEntity(Entity a)
            {
                for (int i = 0; i < L; i++)
                {
                    this.entity[i] = new Gene();
                    this.entity[i].copyGene(a.entity[i]);
                }
            }

            public void randomEntity()
            {
                for (int i = 0; i < L; i++)
                {
                    this.entity[i] = new Gene();
                    this.entity[i].randomGene();
                }
            }

            //计算给定cube的Fscore
            public int calcFscore()
            {
                int[,] newcube = newCube();
                int[,] b = new int[N, N];

                //第一轮，按行赋值
                int t = 1;
                b[0, 0] = t;
                for (int j = 0; j < N; j++)
                {
                    for (int i = 1; i < N; i++)
                    {
                        if (newcube[i - 1, j] == newcube[i, j])
                        {
                            b[i, j] = b[i - 1, j];
                        }
                        else
                        {
                            b[i, j] = ++t;
                        }
                    }
                    if (j == N - 1)
                    {
                        continue;
                    }
                    else
                    {
                        b[0, j + 1] = ++t;
                    }
                }


                //第二遍，按列扫描
                for (int i = 0; i < N; i++)
                {
                    for (int j = 1; j < N; j++)
                    {
                        if (newcube[i, j] == newcube[i, j - 1])
                        {
                            int temp = b[i, j];
                            b[i, j] = b[i, j - 1];
                            for (int k = 0; k < N; k++)
                            {
                                if (b[k, j] == temp)
                                {
                                    b[k, j] = b[i, j - 1];
                                }
                            }
                        }
                    }
                }

                ArrayList alist = new ArrayList();
                for (int i = 0; i < N; i++)
                {
                    for (int j = 0; j < N; j++)
                    {
                        if (!alist.Contains(b[i, j]))
                        {
                            alist.Add(b[i, j]);
                        }
                    }
                }


                return alist.Count;
            }

            //从原始cube通过个体变换得到新的cube
            public int[,] newCube()
            {
                int[,] newcube = new int[N, N];

                //初始化最初cube
                for (int i = 0; i < N; i++)
                {
                    for (int j = 0; j < N; j++)
                    {
                        newcube[i, j] = cube[i, j];
                    }
                }

                //按照每一个基因对cube进行旋转操作
                for (int i = 0; i < L; i++)
                {
                    int x = entity[i].x;
                    int y = entity[i].y;
                    int radix = entity[i].radix;
                    int func = entity[i].func;
                    int[,] b = new int[2 * radix, 2 * radix];

                    switch (func)
                    {
                        //转90度
                        case 0:
                            for (int ay = y - radix, bx = radix + radix - 1; ay < y + radix; ay++, bx--)
                            {
                                for (int ax = x - radix, by = 0; ax < x + radix; ax++, by++)
                                {
                                    b[bx, by] = newcube[ax, ay];
                                }
                            }
                            for (int ax = x - radix, bx = 0; ax < x + radix; ax++, bx++)
                            {
                                for (int ay = y - radix, by = 0; ay < y + radix; ay++, by++)
                                {
                                    newcube[ax, ay] = b[bx, by];
                                }
                            }
                            break;
                        //转180度
                        case 1:
                            for (int ay = y - radix, by = radix + radix - 1; ay < y + radix; ay++, by--)
                            {
                                for (int ax = x - radix, bx = radix + radix - 1; ax < x + radix; ax++, bx--)
                                {
                                    b[bx, by] = newcube[ax, ay];
                                }
                            }
                            for (int ax = x - radix, bx = 0; ax < x + radix; ax++, bx++)
                            {
                                for (int ay = y - radix, by = 0; ay < y + radix; ay++, by++)
                                {
                                    newcube[ax, ay] = b[bx, by];
                                }
                            }
                            break;
                        //转270度
                        case 2:
                            for (int ay = y - radix, bx = 0; ay < y + radix; ay++, bx++)
                            {
                                for (int ax = x - radix, by = radix + radix - 1; ax < x + radix; ax++, by--)
                                {
                                    b[bx, by] = newcube[ax, ay];
                                }
                            }
                            for (int ax = x - radix, bx = 0; ax < x + radix; ax++, bx++)
                            {
                                for (int ay = y - radix, by = 0; ay < y + radix; ay++, by++)
                                {
                                    newcube[ax, ay] = b[bx, by];
                                }
                            }
                            break;
                    }
                }


                return newcube;
            }
        }

        /// <summary>
        /// 种群，包含MIND个个体
        /// </summary>
        public class Population
        {
            public Entity[] population;
            public Entity[] nextPopulation;
            public int[] Fscore;
            public int[] chunkNum;
            public int tf;
            public int tfIndex;

            public Population()
            {

            }

            public int calcFscore()
            {
                Fscore = new int[MIND];
                chunkNum = new int[MIND];
                int sum = 0;
                tf = 0;
                for (int i = 0; i < MIND; i++)
                {
                    chunkNum[i] = population[i].calcFscore();
                    Fscore[i] = chunkNum[i] * chunkNum[i];
                    if (chunkNum[i] > tf)
                    {
                        tf = chunkNum[i];
                        tfIndex = i;
                    }
                }

                for (int i = 0; i < MIND; i++)
                {
                    Fscore[i] = tf*tf - Fscore[i];
                    sum += Fscore[i];
                }

                return sum;
            }

            //生成初始种群
            public void init()
            {
                population = new Entity[MIND];
                for (int i = 0; i < MIND; i++)
                {
                    population[i] = new Entity();
                    population[i].randomEntity();
                }
            }

            //种群衍化
            public void deviration()
            {
                int iterCount = 0;
                nextPopulation = new Entity[MIND];
                int sum = calcFscore();
                Entity totalBestEntity = new Entity();
                int totalBestChunck = N * N;

                while (iterCount < MAXGEN)
                {
                    //产生下一代种群
                    for (int i = 0; i < MIND; i++)
                    {
                        //轮盘选择

                        int p = rand.Next(0, sum);
                        for (int k = 0; k < MIND; k++)
                        {
                            if (p - Fscore[k] < 0)
                            {
                                nextPopulation[i] = new Entity();
                                nextPopulation[i].copyEntity(population[k]);
                                break;
                            }
                            else
                            {
                                p -= Fscore[k];
                            }
                        }
                    }

                    //对种群进行杂交和变异
                    for (int i = 0; i < MIND; i++)
                    {
                        double p = rand.NextDouble();

                        //杂交过程
                        if (p < GGAP)
                        {
                            int j;
                            do
                            {
                                j = rand.Next(0, N);
                            } while (j == i);

                            //对i和j进行杂交
                            int q = rand.Next(0, L);
                            //Entity tempEntity = new Entity(nextPopulation[i]);
                            Entity tempEntity = new Entity();
                            tempEntity.copyEntity(nextPopulation[i]);
                            for (int k = q; k < L; k++)
                            {
                                //(nextPopulation[i]).entity[k] = new Gene((nextPopulation[j]).entity[k]);
                                //(nextPopulation[j]).entity[k] = new Gene(tempEntity.entity[k]);
                                (nextPopulation[i]).entity[k].copyGene((nextPopulation[j]).entity[k]);
                                (nextPopulation[j]).entity[k].copyGene(tempEntity.entity[k]);
                            }

                            //对杂交后的i, j个体进行变异
                            for (int k = 0; k < L; k++)
                            {
                                double pmk = rand.NextDouble();
                                if (pmk < Pm)
                                {
                                    (nextPopulation[i]).entity[k] = new Gene();
                                    (nextPopulation[i]).entity[k].randomGene();
                                }

                                pmk = rand.NextDouble();
                                if (pmk < Pm)
                                {
                                    (nextPopulation[j]).entity[k] = new Gene();
                                    (nextPopulation[j]).entity[k].randomGene();
                                }
                            }
                        }
                    }//杂交变异过程结束


                    for (int i = 0; i < MIND; i++)
                    {
                        population[i].copyEntity(nextPopulation[i]);
                    }

                    sum = calcFscore();
                    iterCount++;

                    System.Console.Write("[" + iterCount + "]");
                    int minChunck = printFscore();
                    Entity bestentity = getBestEntity(minChunck);
                    sw.Write(minChunck + " ");
                    
                    if (minChunck < totalBestChunck)
                    {
                        totalBestEntity.copyEntity(bestentity);
                        totalBestChunck = minChunck;
                    }

                    if (totalBestChunck == MINCHUNCK)
                    {
                        System.Console.WriteLine("***************");
                        System.Console.WriteLine("best chunck num is " + totalBestChunck);
                        
                        for (int i = 0; i < L; i++)
                        {
                            totalBestEntity.entity[i].printGene();
                        }

                        int[,] newcube = totalBestEntity.newCube();
                        for (int j = 0; j < N; j++)
                        {
                            for (int i = 0; i < N; i++)
                            {
                                System.Console.Write(newcube[i, j]);
                            }
                            System.Console.WriteLine();
                        }
                        return;
                    }
                }//end of iteration

                System.Console.WriteLine("***************");
                System.Console.WriteLine("best chunck num is " + totalBestChunck);
                for (int i = 0; i < L; i++)
                {
                    totalBestEntity.entity[i].printGene();
                }

                int[,] tcube = totalBestEntity.newCube();
                for (int j = 0; j < N; j++)
                {
                    for (int i = 0; i < N; i++)
                    {
                        System.Console.Write(tcube[i, j]);
                    }
                    System.Console.WriteLine();
                }
            }


            public int printFscore()
            {
                int minChunck = N*N;
                for (int i = 0; i < MIND; i++)
                {
                    int f = chunkNum[i];
                    if (f < minChunck)
                        minChunck = f;

                    System.Console.Write(Fscore[i] + " ");
                }
                System.Console.WriteLine();
                System.Console.WriteLine("min chunck: " + minChunck);
                return minChunck;
            }


            public Entity getBestEntity(int minChunck)
            {
                for (int i = 0; i < MIND; i++)
                {
                    if (chunkNum[i] == minChunck)
                    {
                        return population[i];
                    }
                }

                return null;
            }
        }//end of class Population
    }

}
